// 数据范围10^9次方，不能直接遍历
// 采用快速幂的方法进行
//                                 {
// 可以发现, [A_(n - 1), A_(n)]  *   {0, 1},  = [A_(n), A_(n + 1)]
//                                   {1, 1}
//                                  }
// 所以， A_(n) = A_0 * F^n

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n;
const int mod = 10000;

void mul(int a[][2], int f[][2])
{
    int c[2][2] = {0};
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            for (int k = 0; k < 2; ++k)
                c[i][j] = (c[i][j] + a[i][k] * f[k][j]) % mod;
    memcpy(a, c, sizeof c);
}

int fib(int n)
{
    int a[2][2] = {0, 1, 0, 0};
    int f[2][2] = {0, 1, 1, 1};
    while (n)
    {
        if (n & 1)
            mul(a, f);
        mul(f, f);
        n >>= 1;
    }
    return a[0][0];
}

int main()
{
    while (cin >> n, ~n)
        cout << fib(n) << endl;
    return 0;
}